package com.leetcode.动态规划.买卖股票的最佳时机;

/**
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 * 
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 * 
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 * 
 * 对这道题来讲，贪心算法比动态规划更好
 * @author LZF
 *
 */
public class L121买卖股票的最佳时机 {
	// 1.贪心算法
	public int maxProfit_1(int[] prices) {
		int low = Integer.MAX_VALUE;
		int result = 0;
		for (int i = 0; i < prices.length; i++) {
			low = Math.min(low, prices[i]);// 取当天或之前的股票的最小值
			result = Math.max(result, prices[i] - low);// 取当天卖出股票或之前卖出股票的最大值
		}
		return result;
	}

	// 2.动态规划，原理与贪心一样
	public int maxProfit_2(int[] prices) {

		if (prices.length == 0)
			return 0;

		int[][] dp = new int[prices.length][2];
		dp[0][0] = -prices[0];
//        dp[0][1] = 0;
		for (int i = 1; i < prices.length; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);// 取当天或之前的股票的最小值，这里存的是负数，因此取最大值
			dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);// 取当天卖出股票或之前卖出股票的最大值
		}
		return dp[prices.length - 1][1];
	}

	// 3. 动态dp的优化，实际上影响dp[i]的只有dp[i - 1]
	public int maxProfit_3(int[] prices) {

		if (prices.length == 0)
			return 0;

		int[][] dp = new int[2][2];
		dp[0][0] = -prices[0];
//        dp[0][1] = 0;
		for (int i = 1; i < prices.length; i++) {
			dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], -prices[i]);// 取当天或之前的股票的最小值，这里存的是负数，因此取最大值
			dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);// 取当天卖出股票或之前卖出股票的最大值
		}
		return dp[(prices.length - 1) % 2][1];
	}
}
